//
// Created by lanlu on 2025/8/4.
//

#include <algorithm>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &nums)
    {
        // 排序方便去重
        sort(nums.begin(), nums.end());

        // 最终结果
        vector<vector<int> > result;
        // 当确定nums[i]的值 剩下的问题就是 查找两个数之和 等于-nums[i]
        for (int i = 0; i < nums.size() - 2; i++)
        {
            // 如果nums[i]能够找到有效的三元组 那么此时它是第一个元素
            // 要跳过重复的元素 就是判断是否有连续且相等的值
            // [-1,0,1,2,-1,-4]
            // sort
            // [-4,-1,-1,0,1,2]
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            // 使用map存储元素和元素的索引
            unordered_map<int, int> map;
            // i确定之后 变成两数之和
            int target = 0 - nums[i];
            for (int j = i + 1; j < nums.size(); j++)
            {
                // j确定之后 只需要找最后一个数
                int needNum = target - nums[j];
                // 判断map中是否存在needNum
                if (map.find(needNum) != map.end())
                {
                    // 如果存在 三个元素都找到了 且needNum <= nums[j]
                    vector<int> arr = {nums[i], needNum, nums[j]};
                    // 如果在set中不存在 三元组第一次出现 存入结果集中
                    result.push_back(arr);

                    // 跳过重复的nums[j]
                    while (j + 1 < nums.size() && nums[j] == nums[j + 1])
                    {
                        j++;
                    }
                }
                // 将元素存入到哈希表
                map[nums[j]] = j;
            }
        }

        return result;
    }
};

int main()
{
    Solution s;
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int> > result = s.threeSum(nums);
    for (vector<int> v: result)
    {
        for (int i: v)
        {
            cout << i << " ";
        }
        cout << endl;
    }
}
